//1.无优化
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n+1, false);
        dp[0]=true;
        unordered_map<string, int> hashmap;
        for(auto& e: wordDict) {
            hashmap[e]++;
        }

        for(int i = 1; i <= n; ++i) {
            for(int j = 0; j < i; ++j) {
                if(dp[j] && hashmap.count(s.substr(j, i-j))) {
                    dp[i]=true;
                    break;
                }
                    
            }
        }

        return dp[n];
    }
};
//2.
/*
我们只需要检查 长度 ≤ maxLen 的子串 s[j:i]。再长就没必要检查，影响效率
子串长度 = i - j
所以要求 i - j ≤ maxLen → j ≥ i - maxLen
*/
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n+1, false);
        dp[0] = true;

        unordered_set<string> dict(wordDict.begin(), wordDict.end());

        // 计算字典中最长单词的长度
        int maxLen = 0;
        for (auto &e : wordDict) {
            maxLen = max(maxLen, (int)e.size());  //不加int,就是max(int,size_t)
            // template<class T> const T& max(const T& a, const T& b);
        }

        for (int i = 1; i <= n; ++i) {
            // 剪枝：只检查长度 <= maxLen 的子串
            for (int j = max(0, i - maxLen); j < i; ++j) {
                if (dp[j] && dict.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};




